/*
 * Copyright (c) 2016-2021, Hangzhou Qulian Technology Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "ecc.h"

// ----------------------------------------------
// the code will try to guess it based on compiler macros
// when uECC_PLATFORM is not defined.
// ----------------------------------------------
#ifndef uECC_PLATFORM
#if __AVR__
    #define uECC_PLATFORM uECC_avr
#elif defined(__thumb2__) || defined(_M_ARMT) // I think MSVC only supports Thumb-2 targets
    #define uECC_PLATFORM uECC_arm_thumb2
#elif defined(__thumb__)
    #define uECC_PLATFORM uECC_arm_thumb
#elif defined(__arm__) || defined(_M_ARM)
    #define uECC_PLATFORM uECC_arm
#elif defined(__i386__) || defined(_M_IX86) || defined(_X86_) || defined(__I86__)
    #define uECC_PLATFORM uECC_x86
#elif defined(__amd64__) || defined(_M_X64)
    #define uECC_PLATFORM uECC_x86_64
#else
    #define uECC_PLATFORM uECC_arch_other
#endif
#endif
// ----------------------------------------------
// uECC_WORD_SIZE will be automatically set based on your platform
// when it is not explicitly defined.
// ----------------------------------------------
#ifndef uECC_WORD_SIZE
#if uECC_PLATFORM == uECC_avr
    #define uECC_WORD_SIZE 1
#elif (uECC_PLATFORM == uECC_x86_64)
    #define uECC_WORD_SIZE 8
#else
    #define uECC_WORD_SIZE 4
#endif
#endif
// Check uECC_WORD_SIZE
#if (uECC_WORD_SIZE != 4) && (uECC_WORD_SIZE != 8)
    #error "Unsupported value for uECC_WORD_SIZE"
#endif
#if (uECC_ASM && (uECC_PLATFORM == uECC_avr) && (uECC_WORD_SIZE != 1))
    #error "uECC_WORD_SIZE must be 1 when using AVR asm"
#endif
#if (uECC_ASM && (uECC_PLATFORM == uECC_arm || uECC_PLATFORM == uECC_arm_thumb) && (uECC_WORD_SIZE != 4))
    #error "uECC_WORD_SIZE must be 4 when using ARM asm"
#endif
// ----------------------------------------------
// system define
// ----------------------------------------------
#if __STDC_VERSION__ >= 199901L
    #define RESTRICT restrict
#else
    #define RESTRICT
#endif

#ifndef uECC_SUPPORTS_INT128
#if defined(__SIZEOF_INT128__) || ((__clang_major__ * 100 + __clang_minor__) >= 302)
#define uECC_SUPPORTS_INT128 1
#else
#define uECC_SUPPORTS_INT128 0
#endif
#endif
// ----------------------------------------------
// Global parameter definition
// ----------------------------------------------
#if (uECC_WORD_SIZE == 4)
    #define HIGH_BIT_SET 0x80000000
    #define uECC_WORDS   8
    #define Curve_P   {0xFFFFFC2F, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
    #define Curve_B   {0x00000007, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000}
    #define Curve_G   { \
                      {0x16F81798, 0x59F2815B, 0x2DCE28D9, 0x029BFCDB, 0xCE870B07, 0x55A06295, 0xF9DCBBAC, 0x79BE667E}, \
                      {0xFB10D4B8, 0x9C47D08F, 0xA6855419, 0xFD17B448, 0x0E1108A8, 0x5DA4FBFC, 0x26A3C465, 0x483ADA77}}
    #define Curve_N   {0xD0364141, 0xBFD25E8C, 0xAF48A03B, 0xBAAEDCE6, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
    // Limbs of half the secp256k1 order
    #define Curve_N_H {0x681B20A0, 0xDFE92F46, 0x57A4501D, 0x5D576E73, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x7FFFFFFF}
#elif (uECC_WORD_SIZE == 8)
    #define HIGH_BIT_SET 0x8000000000000000ull
    #define uECC_WORDS   4
    #define Curve_P   {0xFFFFFFFEFFFFFC2Full, 0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFFFFFFFFFFull}
    #define Curve_B   {0x0000000000000007ull, 0x0000000000000000ull, 0x0000000000000000ull, 0x0000000000000000ull}
    #define Curve_G   { \
                      {0x59F2815B16F81798ull, 0x029BFCDB2DCE28D9ull, 0x55A06295CE870B07ull, 0x79BE667EF9DCBBACull}, \
                      {0x9C47D08FFB10D4B8ull, 0xFD17B448A6855419ull, 0x5DA4FBFC0E1108A8ull, 0x483ADA7726A3C465ull}}
    #define Curve_N   {0xBFD25E8CD0364141ull, 0xBAAEDCE6AF48A03Bull, 0xFFFFFFFFFFFFFFFEull, 0xFFFFFFFFFFFFFFFFull}
    // Limbs of half the secp256k1 order
    #define Curve_N_H {0xDFE92F46681B20A0ull, 0x5D576E7357A4501Dull, 0xFFFFFFFFFFFFFFFFull, 0x7FFFFFFFFFFFFFFFull}
#endif

#define uECC_WORD_BITS (uECC_WORD_SIZE * 8)  // Number of bits in a word
// ----------------------------------------------
// ecc type definition
// ----------------------------------------------
typedef ql_int32_t  uECC_wordcount_t;
typedef ql_int32_t  uECC_swordcount_t;
typedef ql_int32_t  uECC_bitcount_t;
typedef ql_int32_t  uECC_cmpresult_t;
typedef ql_int32_t  uECC_scalar_t;
typedef ql_void_t   uECC_void_t;
typedef ql_int32_t  uECC_size_t;
typedef ql_err_t    uECC_err_t;
typedef ql_bool_t   uECC_bool_t;
// ----- 1 word = 4 byte -----
#if (uECC_WORD_SIZE == 4)
    typedef ql_uint8_t  uECC_byte_t;
    typedef ql_uint32_t uECC_word_t;
    typedef ql_uint64_t uECC_dword_t;
// ----- 1 word = 8 byte -----
#elif (uECC_WORD_SIZE == 8)
    typedef ql_uint8_t        uECC_byte_t;
    typedef ql_uint32_t       uECC_hword_t;
    typedef ql_uint64_t       uECC_word_t;
#if uECC_SUPPORTS_INT128
    typedef unsigned __int128 uECC_dword_t;
#endif
#endif

// ----------------------------------------------
// Elliptic curve type definition
// ----------------------------------------------
typedef struct uECC_point_t
{
    uECC_word_t x[uECC_WORDS];
    uECC_word_t y[uECC_WORDS];
} uECC_point_t;

static uECC_word_t  curve_p[uECC_WORDS]   = Curve_P;
static uECC_word_t  curve_b[uECC_WORDS]   = Curve_B;
static uECC_point_t curve_G               = Curve_G;
static uECC_word_t  curve_n[uECC_WORDS]   = Curve_N;
static uECC_word_t  curve_n_h[uECC_WORDS] = Curve_N_H;

// ----------------------------------------------
// Get random number function
// ----------------------------------------------
// Windows System
#if (defined(_WIN32) || defined(_WIN64))
#include <windows.h>
#include <wincrypt.h>
static uECC_err_t default_RNG(uECC_byte_t *p_dest, uECC_bitcount_t p_size)
{
	for (uECC_size_t i = 0; i < p_size; i++) {
		uECC_byte_t randByte = rand()%(255);
		p_dest[i] = randByte;
	}
    return ECC_SUCCESS;
}

// Unix System
#elif defined(unix) || defined(__linux__) || defined(__unix__) || defined(__unix) || \
    (defined(__APPLE__) && defined(__MACH__)) || defined(uECC_POSIX)
#include <sys/types.h>
#include <fcntl.h>
#include <unistd.h>
#ifndef O_CLOEXEC
    #define O_CLOEXEC 0
#endif
static uECC_err_t default_RNG(uECC_byte_t *p_dest, uECC_bitcount_t p_size)
{
    uECC_size_t l_fd = open("/dev/urandom", O_RDONLY | O_CLOEXEC);
    if(l_fd == -1)
    {
        l_fd = open("/dev/random", O_RDONLY | O_CLOEXEC);
        if(l_fd == -1)
        {
            return ECC_ERR_RNG_NOT_GENERATE;
        }
    }
    char *l_ptr = (char *)p_dest;
    ssize_t l_left = p_size;
    while(l_left > 0)
    {
        ssize_t l_read = read(l_fd, l_ptr, (size_t)l_left);
        if(l_read <= 0)
        { // read failed
            close(l_fd);
            return 0;
        }
        l_left -= l_read;
        l_ptr += l_read;
    }
    close(l_fd);
    return ECC_SUCCESS;
}

// Some other platform
#else
static uECC_err_t default_RNG(uECC_byte_t *p_dest, uECC_bitcount_t p_size) {
    return ECC_ERR_RNG_NOT_GENERATE;
}
#endif

// Set RNG Function from default_RNG
static uECC_RNG_Function g_rng = &default_RNG;
uECC_void_t uEccSetRng(uECC_RNG_Function p_rng) {
    g_rng = p_rng;
}

uECC_void_t rfc_rng(uECC_byte_t nonce32[uECC_BYTES], const uECC_byte_t hash[uECC_BYTES], const uECC_byte_t priv_key[uECC_BYTES]){
    rfc6979_nonce(nonce32, hash, priv_key,  NULL, NULL, 0);
}

// ----------------------------------------------
// Big Number Operation
// ----------------------------------------------
// -- Convert p_native(native big number) to p_bytes(bytes) --
static uECC_void_t vli_nativeToBytes(uECC_byte_t *p_bytes, const uECC_word_t *p_native)
{
    uECC_size_t i;
#if uECC_WORD_SIZE == 4
    for(i=0; i<uECC_WORDS; ++i)
    {
        uECC_byte_t *p_digit = p_bytes + 4 * (uECC_WORDS - 1 - i);
        p_digit[0] = (uECC_byte_t)(p_native[i] >> 24);
        p_digit[1] = (uECC_byte_t)(p_native[i] >> 16);
        p_digit[2] = (uECC_byte_t)(p_native[i] >> 8);
        p_digit[3] = (uECC_byte_t)(p_native[i]);
    }
#elif uECC_WORD_SIZE == 8
    for(i=0; i<uECC_WORDS; ++i)
    {
        uECC_byte_t *p_digit = p_bytes + 8 * (uECC_WORDS - 1 - i);
        p_digit[0] = p_native[i] >> 56;
        p_digit[1] = p_native[i] >> 48;
        p_digit[2] = p_native[i] >> 40;
        p_digit[3] = p_native[i] >> 32;
        p_digit[4] = p_native[i] >> 24;
        p_digit[5] = p_native[i] >> 16;
        p_digit[6] = p_native[i] >> 8;
        p_digit[7] = p_native[i];
    }
#endif
}

// -- Convert p_bytes(bytes) to p_native(native big number) --
static uECC_void_t vli_bytesToNative(uECC_word_t *p_native, const uECC_byte_t *p_bytes)
{
    uECC_size_t i;
#if uECC_WORD_SIZE == 4
    for(i=0; i<uECC_WORDS; ++i)
    {
        const uECC_byte_t *p_digit = p_bytes + 4 * (uECC_WORDS - 1 - i);
        p_native[i] = ((uECC_word_t)p_digit[0] << 24) | ((uECC_word_t)p_digit[1] << 16) | ((uECC_word_t)p_digit[2] << 8) | (uECC_word_t)p_digit[3];
    }
#elif uECC_WORD_SIZE == 8
    for(i=0; i<uECC_WORDS; ++i)
    {
        const uECC_byte_t *p_digit = p_bytes + 8 * (uECC_WORDS - 1 - i);
        p_native[i] = ((uECC_word_t)p_digit[0] << 56) | ((uECC_word_t)p_digit[1] << 48) | ((uECC_word_t)p_digit[2] << 40) | ((uECC_word_t)p_digit[3] << 32) |
                      ((uECC_word_t)p_digit[4] << 24) | ((uECC_word_t)p_digit[5] << 16) | ((uECC_word_t)p_digit[6] <<  8) | ( uECC_word_t)p_digit[7];
    }
#endif
}

// -- Clear value--
static uECC_void_t vli_clear(uECC_word_t *p_vli)
{
    uECC_wordcount_t i;
    for(i = 0; i < uECC_WORDS; ++i){
        p_vli[i] = 0;
    }
}

// -- Returns 1 if p_vli == 0 --
static uECC_word_t vli_isZero(const uECC_word_t *p_vli)
{
    uECC_wordcount_t i;
    for(i = 0; i < uECC_WORDS; ++i){
        if(p_vli[i]){
            return 0;
        }
    }
    return 1;
}

// -- Returns nonzero if bit p_bit of p_vli is set --
static uECC_word_t vli_testBit(const uECC_word_t *p_vli, uECC_bitcount_t p_bit)
{
    return (p_vli[p_bit/uECC_WORD_BITS] & ((uECC_word_t)1 << (p_bit % uECC_WORD_BITS)));
}

// -- Counts the number of words in p_vli --
static uECC_wordcount_t vli_numDigits(const uECC_word_t *p_vli, uECC_wordcount_t p_maxWords)
{
    uECC_swordcount_t i;
    // Search from the end until we find a non-zero digit.
    // We do it in reverse because we expect that most digits will be nonzero.
    for(i = (uECC_swordcount_t)p_maxWords-1; i >= 0 && p_vli[i] == 0; --i){}
    return (uECC_wordcount_t)(i + 1);
}

// -- Counts the number of bits required to represent p_vli --
static uECC_bitcount_t vli_numBits(const uECC_word_t *p_vli, uECC_wordcount_t p_maxWords)
{
    uECC_word_t i;
    uECC_word_t l_digit;
    uECC_wordcount_t l_numDigits = vli_numDigits(p_vli, p_maxWords);
    if(l_numDigits == 0){
        return 0;
    }
    l_digit = p_vli[l_numDigits - 1];
    for(i = 0; l_digit; ++i){
        l_digit >>= 1;
    }
    return ((uECC_bitcount_t)(l_numDigits - 1) * uECC_WORD_BITS + (uECC_bitcount_t)i);
}

// -- Sets p_dest = p_src --
static uECC_void_t vli_set(uECC_word_t *p_dest, const uECC_word_t *p_src)
{
    uECC_wordcount_t i;
    for(i=0; i<uECC_WORDS; ++i){
        p_dest[i] = p_src[i];
    }
}

// -- Returns sign of p_left - p_right --
static uECC_cmpresult_t vli_cmp(uECC_word_t *p_left, uECC_word_t *p_right)
{
    uECC_swordcount_t i;
    for(i = uECC_WORDS-1; i >= 0; --i){
        if(p_left[i] > p_right[i]){
            return 1;
        }
        else if(p_left[i] < p_right[i]){
            return -1;
        }
    }
    return 0;
}

// -- Computes p_vli = p_vli >> 1 --
static uECC_void_t vli_rshift1(uECC_word_t *p_vli)
{
    uECC_word_t *l_end = p_vli;
    uECC_word_t l_carry = 0;
    p_vli += uECC_WORDS;
    while(p_vli-- > l_end){
        uECC_word_t l_temp = *p_vli;
        *p_vli = (l_temp >> 1) | l_carry;
        l_carry = l_temp << (uECC_WORD_BITS - 1);
    }
}

// -- Computes p_result = p_left + p_right, returning carry. Can modify in place --
static uECC_word_t vli_add(uECC_word_t *p_result, uECC_word_t *p_left, uECC_word_t *p_right)
{
    uECC_word_t l_carry = 0;
    uECC_wordcount_t i;
    for(i = 0; i < uECC_WORDS; ++i){
        uECC_word_t l_sum = p_left[i] + p_right[i] + l_carry;
        if(l_sum != p_left[i]){
            l_carry = (l_sum < p_left[i]);
        }
        p_result[i] = l_sum;
    }
    return l_carry;
}

// -- Computes p_result = p_left - p_right, returning borrow. Can modify in place --
static uECC_word_t vli_sub_multiple(uECC_word_t *p_result, uECC_word_t *p_left, uECC_word_t *p_right, uECC_wordcount_t WordsMultiple)
{
    uECC_word_t l_borrow = 0;
    uECC_wordcount_t i;
    for(i = 0; i < uECC_WORDS * WordsMultiple; ++i){
        uECC_word_t l_diff = p_left[i] - p_right[i] - l_borrow;
        if(l_diff != p_left[i]){
            l_borrow = (l_diff > p_left[i]);
        }
        p_result[i] = l_diff;
    }
    return l_borrow;
}
#define vli_sub(result, left, right) vli_sub_multiple((result), (left), (right), 1)

// -- Compute each word mul result, maintaining the carries --
static uECC_void_t mul2add(uECC_word_t a, uECC_word_t b, uECC_word_t *r0, uECC_word_t *r1, uECC_word_t *r2)
{
#if uECC_WORD_SIZE == 8 && !uECC_SUPPORTS_INT128
    uECC_word_t a0 = a & 0xffffffffull;
    uECC_word_t a1 = a >> 32;
    uECC_word_t b0 = b & 0xffffffffull;
    uECC_word_t b1 = b >> 32;

    uECC_word_t i0 = a0 * b0;
    uECC_word_t i1 = a0 * b1;
    uECC_word_t i2 = a1 * b0;
    uECC_word_t i3 = a1 * b1;

    uECC_word_t p0, p1;
    i2 += (i0 >> 32);
    i2 += i1;
    if(i2 < i1){ // overflow
        i3 += 0x100000000ull;
    }
    p0 = (i0 & 0xffffffffull) | (i2 << 32);
    p1 = i3 + (i2 >> 32);

    *r0 += p0;
    *r1 += (p1 + (*r0 < p0));
    *r2 += ((*r1 < p1) || (*r1 == p1 && *r0 < p0));
#else
    uECC_dword_t p = (uECC_dword_t)a * b;
    uECC_dword_t r01 = ((uECC_dword_t)(*r1) << uECC_WORD_BITS) | *r0;
    r01 += p;
    *r2 += (r01 < p);
    *r1 = r01 >> uECC_WORD_BITS;
    *r0 = (uECC_word_t)r01;
#endif
}

// -- Computes p_result = p_left * p_right --
static uECC_void_t vli_mult(uECC_word_t *p_result, uECC_word_t *p_left, uECC_word_t *p_right)
{
    uECC_word_t r0 = 0;
    uECC_word_t r1 = 0;
    uECC_word_t r2 = 0;
    uECC_wordcount_t i, k;
    // Compute each digit of p_result in sequence, maintaining the carries
    for(k = 0; k < uECC_WORDS; ++k){
        for(i = 0; i <= k; ++i){
            mul2add(p_left[i], p_right[k-i], &r0, &r1, &r2);
        }
        p_result[k] = r0;
        r0 = r1;
        r1 = r2;
        r2 = 0;
    }
    for(k = uECC_WORDS; k < uECC_WORDS*2 - 1; ++k){
        for(i = (k + 1) - uECC_WORDS; i<uECC_WORDS; ++i){
            mul2add(p_left[i], p_right[k-i], &r0, &r1, &r2);
        }
        p_result[k] = r0;
        r0 = r1;
        r1 = r2;
        r2 = 0;
    }
    p_result[uECC_WORDS*2 - 1] = r0;
}

// -- Computes p_result = p_left * p_left --
#define vli_square(result, left) vli_mult((result), (left), (left))

// ----------------------------------------------
// Big Number Mod Operation
// ----------------------------------------------
// -- Computes p_result = (p_left + p_right) % p_mod --
// -- Assumes that p_left < p_mod and p_right < p_mod, p_result != p_mod --
static uECC_void_t vli_modAdd(uECC_word_t *p_result, uECC_word_t *p_left, uECC_word_t *p_right, uECC_word_t *p_mod)
{
    uECC_word_t l_carry = vli_add(p_result, p_left, p_right);
    if(l_carry || vli_cmp(p_result, p_mod) >= 0){
        // p_result > p_mod (p_result = p_mod + remainder), so subtract p_mod to get remainder
        vli_sub(p_result, p_result, p_mod);
    }
}

// -- Computes p_result = (p_left - p_right) % p_mod --
// -- Assumes that p_left < p_mod and p_right < p_mod, p_result != p_mod --
static uECC_void_t vli_modSub(uECC_word_t *p_result, uECC_word_t *p_left, uECC_word_t *p_right, uECC_word_t *p_mod)
{
    uECC_word_t l_borrow = vli_sub(p_result, p_left, p_right);
    if(l_borrow){
        // In this case, p_result == -diff == (max int) - diff.
        // Since -x % d == d - x, we can get the correct result from p_result + p_mod (with overflow).
        vli_add(p_result, p_result, p_mod);
    }
}
#define vli_modSub_fast(result, left, right) vli_modSub((result), (left), (right), curve_p)

// -- Computes omega --
#if uECC_WORD_SIZE == 4
static uECC_void_t omega_mult(uECC_word_t * RESTRICT p_result, uECC_word_t * RESTRICT p_right)
{
    // Multiply by (2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1)
    uECC_word_t l_carry = 0;
    uECC_size_t i;
    for(i=0; i<uECC_WORDS; ++i) {
        uECC_dword_t p = (uECC_dword_t)0x3D1 * p_right[i] + l_carry;
        p_result[i] = (p & 0xffffffff);
        l_carry = p >> 32;
    }
    p_result[uECC_WORDS] = l_carry;
    p_result[1 + uECC_WORDS] = vli_add(p_result + 1, p_result + 1, p_right); /* add the 2^32 multiple */
}

#elif uECC_WORD_SIZE == 8
static uECC_void_t omega_mult(uECC_word_t * RESTRICT p_result, uECC_word_t * RESTRICT p_right)
{
    uECC_word_t r0 = 0;
    uECC_word_t r1 = 0;
    uECC_word_t r2 = 0;
    uECC_wordcount_t k;
    // Multiply by (2^32 + 2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1)
    for(k = 0; k < uECC_WORDS; ++k) {
        mul2add(0x1000003D1ull, p_right[k], &r0, &r1, &r2);
        p_result[k] = r0;
        r0 = r1;
        r1 = r2;
        r2 = 0;
    }
    p_result[uECC_WORDS] = r0;
}
#endif

// -- Computes p_result = p_product % curve_p --
// -- see http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf page 354 --
// -- Note that this only works if log2(omega) < log2(p)/2 --
static uECC_void_t vli_mmod_fast(uECC_word_t *RESTRICT p_result, uECC_word_t *RESTRICT p_product)
{
    uECC_word_t l_tmp[2*uECC_WORDS];
    uECC_word_t l_carry;

    vli_clear(l_tmp);
    vli_clear(l_tmp + uECC_WORDS);

    omega_mult(l_tmp, p_product + uECC_WORDS);      // (Rq, q) = q * c
    l_carry = vli_add(p_result, p_product, l_tmp);  // (C, r) = r + q
    if(!vli_isZero(l_tmp + uECC_WORDS)) {      // if Rq > 0 */
        vli_clear(p_product);
        omega_mult(p_product, l_tmp + uECC_WORDS);  // Rq*c
        l_carry += vli_add(p_result, p_result, p_product); // (C1, r) = r + Rq*c
    }
    while(l_carry > 0){
        --l_carry;
        vli_sub(p_result, p_result, curve_p);
    }
    if(vli_cmp(p_result, curve_p) > 0) {
        vli_sub(p_result, p_result, curve_p);
    }
}

// -- Computes p_result = (p_left * p_right) % curve_p --
static uECC_void_t vli_modMult_fast(uECC_word_t *p_result, uECC_word_t *p_left, uECC_word_t *p_right)
{
    uECC_word_t l_product[2 * uECC_WORDS];
    vli_mult(l_product, p_left, p_right);
    vli_mmod_fast(p_result, l_product);
}

// -- Computes p_result = (p_left * p_right) % curve_n --
static uECC_void_t vli_modMult_n(uECC_word_t *p_result, uECC_word_t *p_left, uECC_word_t *p_right)
{
    uECC_word_t l_product[2 * uECC_WORDS];
    uECC_word_t l_modMultiple[2 * uECC_WORDS];
    uECC_word_t l_tmp[2 * uECC_WORDS];
    uECC_word_t *v[2] = {l_tmp, l_product};

    vli_mult(l_product, p_left, p_right);
    vli_set(l_modMultiple + uECC_WORDS, curve_n); // works if curve_n has its highest bit set
    vli_clear(l_modMultiple);

    uECC_bitcount_t i;
    uECC_word_t l_index = 1;
    for(i=0; i<=uECC_BYTES * 8; ++i)
    {
        uECC_word_t l_borrow = vli_sub_multiple(v[1-l_index], v[l_index], l_modMultiple, 2);
        l_index = !(l_index ^ l_borrow); // Swap the index if there was no borrow

        vli_rshift1(l_modMultiple);
        l_modMultiple[uECC_WORDS-1] |= l_modMultiple[uECC_WORDS] << (uECC_WORD_BITS - 1);
        vli_rshift1(l_modMultiple + uECC_WORDS);
    }
    vli_set(p_result, v[l_index]);
}

// -- Computes p_result = p_left^2 % curve_p. --
static uECC_void_t vli_modSquare_fast(uECC_word_t *p_result, uECC_word_t *p_left)
{
    uECC_word_t l_product[2 * uECC_WORDS];
    vli_square(l_product, p_left);
    vli_mmod_fast(p_result, l_product);
}

// -- Computes p_result = (1 / p_input) % p_mod. All VLIs are the same size. --
//   See "From Euclid's GCD to Montgomery Multiplication to the Great Divide"
//   https://labs.oracle.com/techrep/2001/smli_tr-2001-95.pdf */
#define EVEN(vli) (!(vli[0] & 1))
static uECC_void_t vli_modInv(uECC_word_t *p_result, uECC_word_t *p_input, uECC_word_t *p_mod)
{
    uECC_word_t a[uECC_WORDS], b[uECC_WORDS], u[uECC_WORDS], v[uECC_WORDS];
    uECC_word_t l_carry;
    uECC_cmpresult_t l_cmpResult;

    if(vli_isZero(p_input)){
        vli_clear(p_result);
        return;
    }

    vli_set(a, p_input);
    vli_set(b, p_mod);
    vli_clear(u);
    u[0] = 1;
    vli_clear(v);
    while((l_cmpResult = vli_cmp(a, b)) != 0) {
        l_carry = 0;
        if(EVEN(a)) {
            vli_rshift1(a);
            if(!EVEN(u)) {
                l_carry = vli_add(u, u, p_mod);
            }
            vli_rshift1(u);
            if(l_carry) {
                u[uECC_WORDS-1] |= HIGH_BIT_SET;
            }
        }
        else if(EVEN(b)) {
            vli_rshift1(b);
            if(!EVEN(v)) {
                l_carry = vli_add(v, v, p_mod);
            }
            vli_rshift1(v);
            if(l_carry) {
                v[uECC_WORDS-1] |= HIGH_BIT_SET;
            }
        }
        else if(l_cmpResult > 0) {
            vli_sub(a, a, b);
            vli_rshift1(a);
            if(vli_cmp(u, v) < 0) {
                vli_add(u, u, p_mod);
            }
            vli_sub(u, u, v);
            if(!EVEN(u)) {
                l_carry = vli_add(u, u, p_mod);
            }
            vli_rshift1(u);
            if(l_carry) {
                u[uECC_WORDS-1] |= HIGH_BIT_SET;
            }
        }
        else {
            vli_sub(b, b, a);
            vli_rshift1(b);
            if(vli_cmp(v, u) < 0) {
                vli_add(v, v, p_mod);
            }
            vli_sub(v, v, u);
            if(!EVEN(v)) {
                l_carry = vli_add(v, v, p_mod);
            }
            vli_rshift1(v);
            if(l_carry) {
                v[uECC_WORDS-1] |= HIGH_BIT_SET;
            }
        }
    }
    vli_set(p_result, u);
}

// -- Compute a = sqrt(a) (mod curve_p) --
static uECC_void_t vli_modSqrt(uECC_word_t *a)
{
    uECC_bitcount_t i;
    uECC_word_t p1[uECC_WORDS] = {1};
    uECC_word_t l_result[uECC_WORDS] = {1};

    // Since curve_p == 3 (mod 4) for all supported curves, we can
    // compute sqrt(a) = a^((curve_p + 1) / 4) (mod curve_p).
    vli_add(p1, curve_p, p1); // p1 = curve_p + 1
    for(i = vli_numBits(p1, uECC_WORDS) - 1; i > 1; --i) {
        vli_modSquare_fast(l_result, l_result);
        if(vli_testBit(p1, i)) {
            vli_modMult_fast(l_result, l_result, a);
        }
    }
    vli_set(a, l_result);
}

// ----------------------------------------------
// Point Operation
// ----------------------------------------------
// -- Returns 1 if p_point is the point at infinity, 0 otherwise --
static uECC_cmpresult_t EccPoint_isZero(uECC_point_t *p_point)
{
    return (vli_isZero(p_point->x) && vli_isZero(p_point->y));
}

// -- Point multiplication algorithm using Montgomery's ladder with co-Z coordinates --
// -- From http://eprint.iacr.org/2011/338.pdf --
static uECC_void_t EccPoint_double_jacobian(uECC_word_t * RESTRICT X1, uECC_word_t * RESTRICT Y1, uECC_word_t * RESTRICT Z1)
{
    /* t1 = X, t2 = Y, t3 = Z */
    uECC_word_t t4[uECC_WORDS];
    uECC_word_t t5[uECC_WORDS];

    if(vli_isZero(Z1)){
        return;
    }
    vli_modSquare_fast(t5, Y1);      // t5 = y1^2
    vli_modMult_fast(t4, X1, t5);    // t4 = x1*y1^2 = A
    vli_modSquare_fast(X1, X1);      // t1 = x1^2
    vli_modSquare_fast(t5, t5);      // t5 = y1^4
    vli_modMult_fast(Z1, Y1, Z1);    // t3 = y1*z1 = z3
    vli_modAdd(Y1, X1, X1, curve_p); // t2 = 2*x1^2
    vli_modAdd(Y1, Y1, X1, curve_p); // t2 = 3*x1^2
    if(vli_testBit(Y1, 0)) {
        uECC_word_t l_carry = vli_add(Y1, Y1, curve_p);
        vli_rshift1(Y1);
        Y1[uECC_WORDS-1] |= l_carry << (uECC_WORD_BITS - 1);
    }
    else {
        vli_rshift1(Y1);
    }
    // t2 = 3/2*(x1^2) = B
    vli_modSquare_fast(X1, Y1);      // t1 = B^2
    vli_modSub(X1, X1, t4, curve_p); // t1 = B^2 - A
    vli_modSub(X1, X1, t4, curve_p); // t1 = B^2 - 2A = x3
    vli_modSub(t4, t4, X1, curve_p); // t4 = A - x3
    vli_modMult_fast(Y1, Y1, t4);    // t2 = B * (A - x3)
    vli_modSub(Y1, Y1, t5, curve_p); // t2 = B * (A - x3) - y1^4 = y3
}

// -- Modify (x1, y1) => (x1 * z^2, y1 * z^3) --
static uECC_void_t apply_z(uECC_word_t * RESTRICT X1, uECC_word_t * RESTRICT Y1, uECC_word_t * RESTRICT Z)
{
    uECC_word_t t1[uECC_WORDS];
    vli_modSquare_fast(t1, Z);    // z^2
    vli_modMult_fast(X1, X1, t1); // x1 * z^2
    vli_modMult_fast(t1, t1, Z);  // z^3
    vli_modMult_fast(Y1, Y1, t1); // y1 * z^3
}

// -- P = (x1, y1) => 2P, (x2, y2) => P' --
static uECC_void_t XYcZ_initial_double(uECC_word_t * RESTRICT X1, uECC_word_t * RESTRICT Y1,
                                uECC_word_t * RESTRICT X2, uECC_word_t * RESTRICT Y2, const uECC_word_t * RESTRICT p_initialZ)
{
    uECC_word_t z[uECC_WORDS];

    vli_set(X2, X1);
    vli_set(Y2, Y1);
    vli_clear(z);
    z[0] = 1;
    if(p_initialZ){
        vli_set(z, p_initialZ);
    }
    apply_z(X1, Y1, z);
    EccPoint_double_jacobian(X1, Y1, z);
    apply_z(X2, Y2, z);
}

// -- Input P = (x1, y1, Z), Q = (x2, y2, Z) --
// -- Output P' = (x1', y1', Z3), P + Q = (x3, y3, Z3) or P => P', Q => P + Q --
static uECC_void_t XYcZ_add(uECC_word_t * RESTRICT X1, uECC_word_t * RESTRICT Y1, uECC_word_t * RESTRICT X2, uECC_word_t * RESTRICT Y2)
{
    // t1 = X1, t2 = Y1, t3 = X2, t4 = Y2
    uECC_word_t t5[uECC_WORDS];

    vli_modSub_fast(t5, X2, X1);    // t5 = x2 - x1
    vli_modSquare_fast(t5, t5);     // t5 = (x2 - x1)^2 = A
    vli_modMult_fast(X1, X1, t5);   // t1 = x1*A = B
    vli_modMult_fast(X2, X2, t5);   // t3 = x2*A = C
    vli_modSub_fast(Y2, Y2, Y1);    // t4 = y2 - y1
    vli_modSquare_fast(t5, Y2);     // t5 = (y2 - y1)^2 = D

    vli_modSub_fast(t5, t5, X1);    // t5 = D - B
    vli_modSub_fast(t5, t5, X2);    // t5 = D - B - C = x3
    vli_modSub_fast(X2, X2, X1);    // t3 = C - B
    vli_modMult_fast(Y1, Y1, X2);   // t2 = y1*(C - B)
    vli_modSub_fast(X2, X1, t5);    // t3 = B - x3
    vli_modMult_fast(Y2, Y2, X2);   // t4 = (y2 - y1)*(B - x3)
    vli_modSub_fast(Y2, Y2, Y1);    // t4 = y3

    vli_set(X2, t5);
}

// -- Input P = (x1, y1, Z), Q = (x2, y2, Z) --
// -- Output P + Q = (x3, y3, Z3), P - Q = (x3', y3', Z3) or P => P - Q, Q => P + Q --
static uECC_void_t XYcZ_addC(uECC_word_t * RESTRICT X1, uECC_word_t * RESTRICT Y1, uECC_word_t * RESTRICT X2, uECC_word_t * RESTRICT Y2)
{
    // t1 = X1, t2 = Y1, t3 = X2, t4 = Y2
    uECC_word_t t5[uECC_WORDS];
    uECC_word_t t6[uECC_WORDS];
    uECC_word_t t7[uECC_WORDS];

    vli_modSub_fast(t5, X2, X1);     // t5 = x2 - x1
    vli_modSquare_fast(t5, t5);      // t5 = (x2 - x1)^2 = A
    vli_modMult_fast(X1, X1, t5);    // t1 = x1*A = B
    vli_modMult_fast(X2, X2, t5);    // t3 = x2*A = C
    vli_modAdd(t5, Y2, Y1, curve_p); // t4 = y2 + y1
    vli_modSub_fast(Y2, Y2, Y1);     // t4 = y2 - y1

    vli_modSub_fast(t6, X2, X1);     // t6 = C - B
    vli_modMult_fast(Y1, Y1, t6);    // t2 = y1 * (C - B)
    vli_modAdd(t6, X1, X2, curve_p); // t6 = B + C
    vli_modSquare_fast(X2, Y2);      // t3 = (y2 - y1)^2
    vli_modSub_fast(X2, X2, t6);     // t3 = x3

    vli_modSub_fast(t7, X1, X2);     // t7 = B - x3
    vli_modMult_fast(Y2, Y2, t7);    // t4 = (y2 - y1)*(B - x3)
    vli_modSub_fast(Y2, Y2, Y1);     // t4 = y3

    vli_modSquare_fast(t7, t5);      // t7 = (y2 + y1)^2 = F
    vli_modSub_fast(t7, t7, t6);     // t7 = x3'
    vli_modSub_fast(t6, t7, X1);     // t6 = x3' - B
    vli_modMult_fast(t6, t6, t5);    // t6 = (y2 + y1)*(x3' - B)
    vli_modSub_fast(Y1, t6, Y1);     // t2 = y3'

    vli_set(X1, t7);
}

// -- Compute point mult --
static uECC_void_t EccPoint_mult(uECC_point_t * RESTRICT p_result, uECC_point_t * RESTRICT p_point,
                          const uECC_word_t * RESTRICT p_scalar, const uECC_word_t * RESTRICT p_initialZ, uECC_bitcount_t p_numBits)
{
    // R0 and R1
    uECC_word_t Rx[2][uECC_WORDS];
    uECC_word_t Ry[2][uECC_WORDS];
    uECC_word_t z[uECC_WORDS];
    uECC_bitcount_t i;
    uECC_word_t nb;

    vli_set(Rx[1], p_point->x);
    vli_set(Ry[1], p_point->y);
    XYcZ_initial_double(Rx[1], Ry[1], Rx[0], Ry[0], p_initialZ);
    for(i = p_numBits - 2; i > 0; --i){
        nb = !vli_testBit(p_scalar, i);
        XYcZ_addC(Rx[1-nb], Ry[1-nb], Rx[nb], Ry[nb]);
        XYcZ_add(Rx[nb], Ry[nb], Rx[1-nb], Ry[1-nb]);
    }
    nb = !vli_testBit(p_scalar, 0);
    XYcZ_addC(Rx[1-nb], Ry[1-nb], Rx[nb], Ry[nb]);
    // Find final 1/Z value
    vli_modSub_fast(z, Rx[1], Rx[0]); // X1 - X0
    vli_modMult_fast(z, z, Ry[1-nb]);    // Yb * (X1 - X0)
    vli_modMult_fast(z, z, p_point->x);         // xP * Yb * (X1 - X0)
    vli_modInv(z, z, curve_p);                  // 1 / (xP * Yb * (X1 - X0))
    vli_modMult_fast(z, z, p_point->y);         // yP / (xP * Yb * (X1 - X0))
    vli_modMult_fast(z, z, Rx[1-nb]);    // Xb * yP / (xP * Yb * (X1 - X0))
    // End 1/Z calculation
    XYcZ_add(Rx[nb], Ry[nb], Rx[1-nb], Ry[1-nb]);
    apply_z(Rx[0], Ry[0], z);
    vli_set(p_result->x, Rx[0]);
    vli_set(p_result->y, Ry[0]);
}

// ----------------------------------------------
// secp256k1 scalar
// ----------------------------------------------
// -- Check if the scalar of secp256k1 is overflow --
uECC_scalar_t uECC_scalar_overflow(const uECC_word_t *a) {
    // secp256k1_scalar_check_overflow
    uECC_size_t yes = 0;
    uECC_size_t no = 0;
#if uECC_WORD_SIZE == 8
    no  |= (a[3] < curve_n[3]); // No need for a > check.
    no  |= (a[2] < curve_n[2]);
    yes |= (a[2] > curve_n[2]) & ~no;
    no  |= (a[1] < curve_n[1]);
    yes |= (a[1] > curve_n[1]) & ~no;
    yes |= (a[0] >= curve_n[0]) & ~no;
#elif uECC_WORD_SIZE == 4
    no  |= (a[7] < curve_n[7]); // No need for a > check.
    no  |= (a[6] < curve_n[6]); // No need for a > check.
    no  |= (a[5] < curve_n[5]); // No need for a > check.
    no  |= (a[4] < curve_n[4]);
    yes |= (a[4] > curve_n[4]) & ~no;
    no  |= (a[3] < curve_n[3]) & ~yes;
    yes |= (a[3] > curve_n[3]) & ~no;
    no  |= (a[2] < curve_n[2]) & ~yes;
    yes |= (a[2] > curve_n[2]) & ~no;
    no  |= (a[1] < curve_n[1]) & ~yes;
    yes |= (a[1] > curve_n[1]) & ~no;
    yes |= (a[0] >= curve_n[0]) & ~no;
#endif
    return yes;
}

// -- Check if the scalar of secp256k1 is high --
uECC_scalar_t uECC_scalar_high(const uECC_word_t *a) {
    // secp256k1_scalar_is_high
    uECC_size_t yes = 0;
    uECC_size_t no = 0;
#if uECC_WORD_SIZE == 8
    no  |= (a[3] < curve_n_h[3]);
    yes |= (a[3] > curve_n_h[3]) & ~no;
    no  |= (a[2] < curve_n_h[2]) & ~yes; // No need for a > check.
    no  |= (a[1] < curve_n_h[1]) & ~yes;
    yes |= (a[1] > curve_n_h[1]) & ~no;
    yes |= (a[0] > curve_n_h[0]) & ~no;
#elif uECC_WORD_SIZE == 4
    no  |= (a[7] < curve_n_h[7]);
    yes |= (a[7] > curve_n_h[7]) & ~no;
    no  |= (a[6] < curve_n_h[6]) & ~yes; // No need for a > check.
    no  |= (a[5] < curve_n_h[5]) & ~yes; // No need for a > check.
    no  |= (a[4] < curve_n_h[4]) & ~yes; // No need for a > check.
    no  |= (a[3] < curve_n_h[3]) & ~yes;
    yes |= (a[3] > curve_n_h[3]) & ~no;
    no  |= (a[2] < curve_n_h[2]) & ~yes;
    yes |= (a[2] > curve_n_h[2]) & ~no;
    no  |= (a[1] < curve_n_h[1]) & ~yes;
    yes |= (a[1] > curve_n_h[1]) & ~no;
    yes |= (a[0] > curve_n_h[0]) & ~no;
#endif
    return yes;
}

// -- secp256k1 scalar negate --
#define LOW(a)   ((uECC_hword_t)(a & 0xffffffff))
#define HIGH(a)  ((uECC_hword_t)((a >> 32) & 0xffffffff))
uECC_void_t uECC_scalar_negate(uECC_word_t *r, const uECC_word_t *a) {


#if uECC_WORD_SIZE == 8 && uECC_SUPPORTS_INT128
    uECC_word_t nonzero = 0xFFFFFFFFFFFFFFFFULL * (vli_isZero(a) == 0);
    uECC_dword_t t = (uECC_dword_t)(~a[0]) + curve_n[0] + 1;
    r[0] = t & nonzero; t >>= 64;
    t += (uECC_dword_t)(~a[1]) + curve_n[1];
    r[1] = t & nonzero; t >>= 64;
    t += (uECC_dword_t)(~a[2]) + curve_n[2];
    r[2] = t & nonzero; t >>= 64;
    t += (uECC_dword_t)(~a[3]) + curve_n[3];
    r[3] = t & nonzero;

#elif uECC_WORD_SIZE == 8 && !uECC_SUPPORTS_INT128
    uECC_hword_t a1[8], r1[8], curve_n1[8];
    for(uECC_size_t i=0; i<4; i++){
        curve_n1[i*2] = (uECC_hword_t)(curve_n[i] & 0xffffffff);
        curve_n1[i*2+1] = (uECC_hword_t)((curve_n[i] >> 32) & 0xffffffff);
        a1[i*2] = (uECC_hword_t)(a[i] & 0xffffffff);
        a1[i*2+1] = (uECC_hword_t)((a[i] >> 32) & 0xffffffff);
    }
    uECC_hword_t nonzero = 0xFFFFFFFFUL * (vli_isZero(a) == 0);
    uECC_word_t t;
    t  = (uECC_word_t)(~a1[0]) + curve_n1[0] + 1;
    r1[0] = t & nonzero; t >>= 32;
    t += (uECC_word_t)(~a1[1]) + curve_n1[1];
    r1[1] = t & nonzero; t >>= 32;
    t += (uECC_word_t)(~a1[2]) + curve_n1[2];
    r1[2] = t & nonzero; t >>= 32;
    t += (uECC_word_t)(~a1[3]) + curve_n1[3];
    r1[3] = t & nonzero; t >>= 32;
    t += (uECC_word_t)(~a1[4]) + curve_n1[4];
    r1[4] = t & nonzero; t >>= 32;
    t += (uECC_word_t)(~a1[5]) + curve_n1[5];
    r1[5] = t & nonzero; t >>= 32;
    t += (uECC_word_t)(~a1[6]) + curve_n1[6];
    r1[6] = t & nonzero; t >>= 32;
    t += (uECC_word_t)(~a1[7]) + curve_n1[7];
    r1[7] = t & nonzero;
    for(uECC_size_t i=0; i<4;i++){
        r[i] = ((uECC_word_t)(r1[i*2+1]) << 32) |  r1[i*2] ;
    }

#elif uECC_WORD_SIZE == 4
    uECC_word_t nonzero = 0xFFFFFFFFUL * (vli_isZero(a) == 0);
    uECC_dword_t t;
    t  = (uECC_dword_t)(~a[0]) + curve_n[0] + 1;
    r[0] = t & nonzero; t >>= 32;
    t += (uECC_dword_t)(~a[1]) + curve_n[1];
    r[1] = t & nonzero; t >>= 32;
    t += (uECC_dword_t)(~a[2]) + curve_n[2];
    r[2] = t & nonzero; t >>= 32;
    t += (uECC_dword_t)(~a[3]) + curve_n[3];
    r[3] = t & nonzero; t >>= 32;
    t += (uECC_dword_t)(~a[4]) + curve_n[4];
    r[4] = t & nonzero; t >>= 32;
    t += (uECC_dword_t)(~a[5]) + curve_n[5];
    r[5] = t & nonzero; t >>= 32;
    t += (uECC_dword_t)(~a[6]) + curve_n[6];
    r[6] = t & nonzero; t >>= 32;
    t += (uECC_dword_t)(~a[7]) + curve_n[7];
    r[7] = t & nonzero;
#endif
}

// ----------------------------------------------
// Public Key
// ----------------------------------------------
// -- Create a public/private key pair --
// -- [Output] p_publicKey  - Will be filled in with the public key. --
// -- [Output] p_privateKey - Will be filled in with the private key. --
// -- Returns value >= 0 if the key pair was generated successfully, value < 0 if an error occurred. --
#define MAX_TRIES  16 // Maximum number of attempts
uECC_err_t uECC_make_key(uECC_byte_t p_publicKey[uECC_BYTES*2], uECC_byte_t p_privateKey[uECC_BYTES])
{
    uECC_point_t l_public;
    uECC_word_t l_private[uECC_WORDS];
    uECC_word_t l_tries = 0;

    do{repeat:
        if(g_rng((uECC_byte_t *)l_private, sizeof(l_private)) != ECC_SUCCESS || (l_tries++ >= MAX_TRIES)){
            return ECC_ERR_RNG_UNSUITABLE;
        }
        if(vli_isZero(l_private)){
            goto repeat;
        }
        EccPoint_mult(&l_public, &curve_G, l_private, 0, vli_numBits(l_private, uECC_WORDS));
    } while(EccPoint_isZero(&l_public));

    vli_nativeToBytes(p_privateKey, l_private);
    vli_nativeToBytes(p_publicKey, l_public.x);
    vli_nativeToBytes(p_publicKey + uECC_BYTES, l_public.y);
    return ECC_SUCCESS;
}

// -- Create a public key --
// -- [Input]  p_privateKey - Your private key. --
// -- [Output] p_publicKey  - Will be filled in with the public key. --
// -- Returns value >= 0 if the public key was generated successfully, value < 0 if an error occurred. --
uECC_err_t uECC_create_pubkey(uECC_byte_t p_publicKey[uECC_BYTES*2], uECC_byte_t p_privateKey[uECC_BYTES])
{
    uECC_point_t l_public;
    uECC_word_t l_private[uECC_WORDS];

    vli_bytesToNative(l_private, p_privateKey);
    EccPoint_mult(&l_public, &curve_G, l_private, 0, vli_numBits(l_private, uECC_WORDS));
    if(EccPoint_isZero(&l_public)){
        return ECC_ERR_PUB_EQUAL_ZERO;
    }
    vli_nativeToBytes(p_publicKey, l_public.x);
    vli_nativeToBytes(p_publicKey + uECC_BYTES, l_public.y);
    return ECC_SUCCESS;
}

// -- compress a public key --
uECC_void_t uECC_compress(const uECC_byte_t p_publicKey[uECC_BYTES*2], uECC_byte_t p_compressed[uECC_BYTES+1])
{
    uECC_wordcount_t i;
    for(i=0; i<uECC_BYTES; ++i){
        p_compressed[i+1] = p_publicKey[i];
    }
    p_compressed[0] = 2 + (p_publicKey[uECC_BYTES * 2 - 1] & 0x01);
}

// -- Decompress a compressed public key --
uECC_void_t uECC_decompress(const uECC_byte_t p_compressed[uECC_BYTES+1], uECC_byte_t p_publicKey[uECC_BYTES*2])
{
    uECC_point_t l_point;
    vli_bytesToNative(l_point.x, p_compressed + 1);
    vli_modSquare_fast(l_point.y, l_point.x);           // r = x^2
    vli_modMult_fast(l_point.y, l_point.y, l_point.x);  // r = x^3
    vli_modAdd(l_point.y, l_point.y, curve_b, curve_p); // r = x^3 + b
    vli_modSqrt(l_point.y);
    if((l_point.y[0] & 0x01) != (p_compressed[0] & 0x01)){
        vli_sub(l_point.y, curve_p, l_point.y);
    }
    vli_nativeToBytes(p_publicKey, l_point.x);
    vli_nativeToBytes(p_publicKey + uECC_BYTES, l_point.y);
}

// ----------------------------------------------
// Generate an signature for a given hash value.
// ----------------------------------------------
uECC_err_t uEccSign(const uECC_byte_t p_privateKey[uECC_BYTES], const uECC_byte_t p_hash[uECC_BYTES], uECC_byte_t p_signature[uECC_BYTES*2+1])
{
    uECC_word_t k[uECC_WORDS];
    uECC_word_t l_tmp[uECC_WORDS];
    uECC_word_t s[uECC_WORDS];
    uECC_word_t *k2[2] = {l_tmp, s};
    uECC_point_t p;
    uECC_byte_t b32[32];

    // Check Private Key
    vli_bytesToNative(k, p_privateKey);
    if(vli_isZero(k)) {
        return ECC_ERR_PRI_EQUAL_ZERO;
    }
    // Generate rng
    rfc_rng(b32, p_hash, p_privateKey);
    vli_bytesToNative(k, b32);
    if(vli_isZero(k)) {
        return ECC_ERR_RNG_EQUAL_ZERO;
    }
#if uECC_WORD_SIZE == 8
    log_debug("k :%016lx%016lx%016lx%016lx",k[3],k[2],k[1],k[0]);
#elif uECC_WORD_SIZE == 4
    log_debug("k :%08lx%08lx%08lx%08lx%08lx%08lx%08lx%08lx",k[7],k[6],k[5],k[4],k[3],k[2],k[1],k[0]);
#endif
    if(vli_cmp(curve_n, k) != 1){
        return ECC_ERR_RNG_UNSUITABLE;
    }
    // make sure that we don't leak timing information about k. See http://eprint.iacr.org/2011/232.pdf
    uECC_word_t l_carry = vli_add(l_tmp, k, curve_n);
    vli_add(s, l_tmp, curve_n);

    EccPoint_mult(&p, &curve_G, k2[!l_carry], 0, (uECC_BYTES * 8) + 1); // p = k * G
    if(vli_cmp(curve_n, p.x) != 1){                                     // r = x1 (mod n)
        vli_sub(p.x, p.x, curve_n);
    }
#if uECC_WORD_SIZE == 8
    log_debug("r :%016lx%016lx%016lx%016lx",p.x[3],p.x[2],p.x[1],p.x[0]);
#elif uECC_WORD_SIZE == 4
    log_debug("r :%08lx%08lx%08lx%08lx%08lx%08lx%08lx%08lx",p.x[7],p.x[6],p.x[5],p.x[4],p.x[3],p.x[2],p.x[1],p.x[0]);
#endif
    if(vli_isZero(p.x)){
        return ECC_ERR_PUB_EQUAL_ZERO;
    }
    vli_modInv(k, k, curve_n);               // k = 1 / rand / k
    vli_nativeToBytes(p_signature, p.x);     // store r
    l_tmp[uECC_WORDS-1] = 0;
    vli_bytesToNative(l_tmp, p_privateKey);  // tmp = d
    s[uECC_WORDS-1] = 0;
    vli_set(s, p.x);
    vli_modMult_n(s, l_tmp, s);              // s = r*d
    vli_bytesToNative(l_tmp, p_hash);
#if uECC_WORD_SIZE == 8
    log_debug("h :%016lx%016lx%016lx%016lx",l_tmp[3],l_tmp[2],l_tmp[1],l_tmp[0]);
#elif uECC_WORD_SIZE == 4
    log_debug("h :%08lx%08lx%08lx%08lx%08lx%08lx%08lx%08lx",l_tmp[7],l_tmp[6],l_tmp[5],l_tmp[4],l_tmp[3],l_tmp[2],l_tmp[1],l_tmp[0]);
#endif
    vli_modAdd(s, l_tmp, s, curve_n);        // s = e + r*d
    vli_modMult_n(s, s, k);                  // s = (e + r*d) / k
#if uECC_WORD_SIZE == 8
    log_debug("s0:%016lx%016lx%016lx%016lx",s[3],s[2],s[1],s[0]);
#elif uECC_WORD_SIZE == 4
    log_debug("s0:%08lx%08lx%08lx%08lx%08lx%08lx%08lx%08lx",s[7],s[6],s[5],s[4],s[3],s[2],s[1],s[0]);
#endif
    // calculate overflow
    uECC_size_t overflow = uECC_scalar_overflow(p.x);
    uECC_byte_t a = (overflow == 1 ? 2 : 0) | ((p.y[0] & 0x01) != 0 ? 1 : 0);
    if(uECC_scalar_high(s) != 0) {
        uECC_scalar_negate(s, s);
        a = a ^ 1;
    }
#if uECC_WORD_SIZE == 8
    log_debug("s :%016lx%016lx%016lx%016lx",s[3],s[2],s[1],s[0]);
#elif uECC_WORD_SIZE == 4
    log_debug("s :%08lx%08lx%08lx%08lx%08lx%08lx%08lx%08lx",s[7],s[6],s[5],s[4],s[3],s[2],s[1],s[0]);
#endif
    log_debug("a :%02x",a);
    p_signature[uECC_BYTES*2] = a;
    vli_nativeToBytes(p_signature + uECC_BYTES, s);
    return ECC_SUCCESS;
}

// ----------------------------------------------
// Verify an ECDSA signature.
// Usage: Compute the hash of the signed data using the same hash as the signer and
//        pass it to this function along with the signer's public key and the signature values (r and s).
// ----------------------------------------------
uECC_err_t uECC_verify(uECC_bool_t* res, const uECC_byte_t p_publicKey[uECC_BYTES*2], const uECC_byte_t p_hash[uECC_BYTES], const uECC_byte_t p_signature[uECC_BYTES*2])
{
    uECC_word_t u1[uECC_WORDS], u2[uECC_WORDS];
    uECC_word_t z[uECC_WORDS];
    uECC_point_t l_public, l_sum;
    uECC_word_t rx[uECC_WORDS];
    uECC_word_t ry[uECC_WORDS];
    uECC_word_t tx[uECC_WORDS];
    uECC_word_t ty[uECC_WORDS];
    uECC_word_t tz[uECC_WORDS];
    uECC_word_t r[uECC_WORDS], s[uECC_WORDS];
    r[uECC_WORDS-1] = 0;
    s[uECC_WORDS-1] = 0;

    vli_bytesToNative(l_public.x, p_publicKey);
    vli_bytesToNative(l_public.y, p_publicKey + uECC_BYTES);
    vli_bytesToNative(r, p_signature);
    vli_bytesToNative(s, p_signature + uECC_BYTES);
    if(vli_isZero(r) || vli_isZero(s)){  // r, s must not be 0.
        return ECC_ERR_SIG_EQUAL_ZERO;
    }
    if(vli_cmp(curve_n, r) != 1 || vli_cmp(curve_n, s) != 1){ // r, s must be < n.
        return ECC_ERR_SIG_BIGGER_N;
    }
    // Calculate u1 and u2.
    vli_modInv(z, s, curve_n);  // Z = s^-1
    u1[uECC_WORDS-1] = 0;
    vli_bytesToNative(u1, p_hash);
    vli_modMult_n(u1, u1, z);   // u1 = e/s
    vli_modMult_n(u2, r, z);    // u2 = r/s
    // Calculate l_sum = G + Q.
    vli_set(l_sum.x, l_public.x);
    vli_set(l_sum.y, l_public.y);
    vli_set(tx, curve_G.x);
    vli_set(ty, curve_G.y);
    vli_modSub_fast(z, l_sum.x, tx);    // Z = x2 - x1
    XYcZ_add(tx, ty, l_sum.x, l_sum.y);
    vli_modInv(z, z, curve_p);               // Z = 1/Z
    apply_z(l_sum.x, l_sum.y, z);
    // Use Shamir's trick to calculate u1*G + u2*Q
    uECC_point_t *l_points[4] = {0, &curve_G, &l_public, &l_sum};
    uECC_bitcount_t l_numBits = (vli_numBits(u1, uECC_WORDS) > vli_numBits(u2, uECC_WORDS) ? vli_numBits(u1, uECC_WORDS) : vli_numBits(u2, uECC_WORDS));

    uECC_point_t *l_point = l_points[(!!vli_testBit(u1, l_numBits-1)) | ((!!vli_testBit(u2, l_numBits-1)) << 1)];
    vli_set(rx, l_point->x);
    vli_set(ry, l_point->y);
    vli_clear(z);
    z[0] = 1;

    uECC_bitcount_t i;
    for(i = l_numBits - 2; i >= 0; --i){
        EccPoint_double_jacobian(rx, ry, z);
        uECC_word_t l_index = (!!vli_testBit(u1, i)) | (uECC_word_t)((!!vli_testBit(u2, i)) << 1);
        l_point = l_points[l_index];
        if(l_point){
            vli_set(tx, l_point->x);
            vli_set(ty, l_point->y);
            apply_z(tx, ty, z);
            vli_modSub_fast(tz, rx, tx);    // Z = x2 - x1
            XYcZ_add(tx, ty, rx, ry);
            vli_modMult_fast(z, z, tz);
        }
    }
    vli_modInv(z, z, curve_p);  // Z = 1/Z
    apply_z(rx, ry, z);
    // v = x1 (mod n)
    if(vli_cmp(curve_n, rx) != 1){
        vli_sub(rx, rx, curve_n);
    }
    // Accept only if v == r.
    *res = (vli_cmp(rx, r) == 0) ? 1 : 0;
    return ECC_SUCCESS;
}


// -- shared secret --
// -- Compute a shared secret given your secret key and someone else's public key. --
// -- Note: It is recommended that you hash the result of uECC_shared_secret() before using it for symmetric encryption or HMAC. --
// -- [Input] p_publicKey  - The public key of the remote party. --
// -- [Input] p_privateKey - Your private key. --
// -- [Output] p_secret - Will be filled in with the shared secret value. --
// -- Returns value >= 0 if the shared secret was generated successfully, value < 0 if an error occurred. --
uECC_err_t uECC_shared_secret(const uECC_byte_t p_publicKey[uECC_BYTES*2], const uECC_byte_t p_privateKey[uECC_BYTES], uECC_byte_t p_secret[uECC_BYTES])
{
    uECC_point_t l_public;
    uECC_word_t l_private[uECC_WORDS];
    uECC_word_t l_random[uECC_WORDS];

    uECC_err_t res = g_rng((uECC_byte_t *)l_random, sizeof(l_random));
    if (res != ECC_SUCCESS) {
        return res;
    }
    vli_bytesToNative(l_private, p_privateKey);
    vli_bytesToNative(l_public.x, p_publicKey);
    vli_bytesToNative(l_public.y, p_publicKey + uECC_BYTES);
    uECC_point_t l_product;
    EccPoint_mult(&l_product, &l_public, l_private, (vli_isZero(l_random) ? 0: l_random), vli_numBits(l_private, uECC_WORDS));
    vli_nativeToBytes(p_secret, l_product.x);

    if(EccPoint_isZero(&l_product))
        return ECC_ERR_SHAREKEY_EQUAL_ZERO;
    else
        return ECC_SUCCESS;
}
